In a data communication system desired to transmit data without any error and a storage device desired to perform data read without any error, and the like, an “error detection code” is used to detect a transmission error and a read error or so.
A “cyclic redundancy check (CRC) code” is one of error detection codes. In a data communication system for performing error detection using the CRC code, a transmission side adds an L-bit remainder obtained by dividing a polynomial corresponding to a K′-bit information bit stream by a generator polynomial for generating a CRC code to an information bit stream to form a K-bit encoded bit stream, and transmits the formed encoded bit stream to a reception side. Therefore, a bit side after the error detection encoding becomes “K=K′+L”, and a remainder obtained by dividing the K-bit encoded bit stream by the generator polynomial becomes “0”. “K′” is an information bit size of one block, i.e., a block size. An L-bit remainder added to each block of the information bit is called a “parity bit”.
The reception side divides the received encoded bit stream by the generator polynomial, determines that “no error occurs” if the remainder is “0” and that “an error occurs” if the remainder is a value “other than 0”, and performs error detection on the received encoded bit stream.
For example, a polynomial B(x) of the K′-bit information bit stream “b=(a0, . . . , ak′−2, ak′−1)” is expressed by Equation (1).B(x)=a0xK′+ . . . +aK′−2x+aK′−1  (1)
A generator polynomial G(x) is expressed by Equation (2).G(x)=g0xL+ . . . +gL−2x+gL−1  (2)
A remainder value Rcrc(x) obtained by dividing the polynomial B(x) illustrated in Equation (1) by the generator polynomial G(x) is expressed by Equation (3). The remainder value Rcrc(x) corresponds to the parity bit.Rcrc(x)=[xLB(x)] mod G(x)=aK′xL−1+ . . . +aK−2x+aK−1  (3)
By adding the Rcrc(x) in which a bit position is adjusted to B(x), a polynomial A(x) illustrated in Equation (4) is obtained. The A(x) corresponds to a polynomial expression of a K-bit encoded bit stream “a=(a0, . . . , ak−2, ak−1)” after the error detection encoding.A(x)=xLB(x)+Rcrc(x)=a0xK+ . . . +aK−2x+aK−1  (4)
The transmission side transmits the encoded bit stream expressed by the polynomial A(x) to the reception side.
Here, the remainder when A(x) is divided by G(x) becomes “0”. Therefore, if a quotient polynomial obtained by dividing A(x) by G(x) is Q(x), then A(x) is expressed by Equation (5).A(x)=Q(x)G(x)  (5)
Because the encoded bit stream A(x) transmitted from the transmission side is affected by noise or so on a transmission path, an error may be contained in an encoded bit stream A^(x) received by the reception side. Therefore, the reception side calculates a remainder R^(x) when the received encoded bit stream A^(x) is divided by the generator polynomial G(x), according to Equation (6).{circumflex over (R)}(x)={circumflex over (A)}(x)mod G(x)  (6)
The reception side determines that “no error occurs” in A^(x) when R^(x) becomes “0”, and determines that “an error occurs” in A^(x) when R^(x) becomes a value “other than 0”.
As a first related technology, there is an error detection device capable of performing error detection on an encoded bit stream, in which the order of the bits is randomized through interleaving, without changing the order and without deinterleaving. The error detection device previously calculates a remainder value when a polynomial corresponding to each bit position (i.e., each normal bit position) in the information bit stream before the interleave processing is divided by the generator polynomial and stores the calculated value in a memory. Each bit in the bit stream is randomly input and bit position information indicating normal bit positions of the bits is also input. The error detection device acquires each remainder value corresponding to the normal bit position of a bit, of the bits in the input bit stream, whose value is not 0 i.e. whose value is 1 from the memory, and cumulatively adds the acquired remainder values. When a cumulative addition result is “0”, the error detection device determines that “no error occurs” in the input bit stream, and determines that “an error occurs” in the input bit stream when the cumulative addition result is a value “other than 0”. In other words, the cumulative addition result of remainder values corresponding to normal bit positions of bits which are not 0, of the bits in the input bit stream, corresponds to R^(x) in Equation (6).
As a second related technology, there is an error detection device capable of reducing the size of the memory in the first related technology. The error detection device stores only remainder values each corresponding to a bit position of “n×P” (n=1, 2, . . . ) of the normal bit positions, where “P” is a predetermined bit interval. For an input bit stream, the error detection device calculates each remainder value corresponding to the “n×P” bit position of the normal bit positions from the memory, in the same manner as the first related technology. On the other hand, the error detection device calculates each remainder value corresponding to a bit position of “n×P+k” (0≦k<P) of the normal bit positions by shifting each remainder value corresponding to the bit position of “n×P” by k bit and dividing the shift result by the generator polynomial. The error detection device cumulatively adds the remainder values acquired from the memory and the remainder values calculated through the shifting and division, and determines whether an error occurs in the input bit stream based on the cumulative addition result, in the same manner as the first related technology.
Examples of related-art are described in Japanese Patent No. 5126230, in International Publication Pamphlet No. WO 2009/019763, in International Publication Pamphlet No. WO 2008/023684, in Japanese Laid-open Patent Publication No. 2009-136025, in Japanese Laid-open Patent Publication No. 2005-006188, in U.S. Patent Application No. 2010/0138725: Specification, in U.S. Patent Application No. 2010/0198892: Specification, and in A. Shibutani, H. Suda, and F. Adachi, “Complexity Reduction of Turbo Decoding”, Proc. IEEE Veh. Tech. Conf. '99 Fall, October 1999.
To improve an error rate characteristic in the data communication system, forward error correction (FEC) may be performed on transmission data. A turbo code may be used as FEC. Moreover, a CRC code and a turbo code may be used in combination with each other. In this case, the transmission side performs turbo encoding on the bit stream after a parity bit or a CRC code is added thereto, and the reception side performs the CRC on the bit stream after turbo decoding. In the turbo decoding, reliability information of the decoding result is used to perform iterative decoding on the same received data. Therefore, in the turbo decoding, the error rate of the decoding result is getting smaller in each iteration of decoding, and an error is eliminated, that is, error free, in the decoding result at the time when the number of times of decoding reaches a certain number of times. Hereinafter, a bit stream after error detection encoding and error correction encoding may be called an “encoded bit stream” and each bit forming the encoded bit stream may be called an “encoded bit”.
In the turbo decoding, particularly, when the error rate in the decoding result becomes small to be close to the error free, the bit whose value is changed from the previous decoding result is limited to some bits in the current decoding result. In other words, the value of the bit whose value is already corrected in the decoding before the last time is not changed, and the bit with the correct value continues to be the bit of the same value since the value is corrected.
On the other hand, when the CRC according to the first or the second related technology is merely applied to the decoding result of the turbo decoding, the acquisition of the same remainder value and the calculation of the same remainder value or the like are iteratively performed on the bit whose value is corrected through iterative decoding. In other words, the duplicate processing in the CRC is repeatedly performed in each iteration of the turbo decoding, and this causes unnecessary processing to occur in the CRC.